﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
//面试题 02.04.分割链表
//提示
//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
//使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//你不需要 保留 每个分区中各节点的初始相对位置。
struct ListNode {
    int val;
    struct ListNode* next;
};
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* Smallhead = NULL, * Bighead = NULL, * Smalltail = NULL, * Bigtail = NULL;
    Smallhead = Smalltail = (struct ListNode*)malloc(sizeof(struct ListNode));
    Bighead = Bigtail = (struct ListNode*)malloc(sizeof(struct ListNode));
    Smalltail->next = NULL;
    Bigtail->next = NULL;
    struct ListNode* src = head;
    while (src != NULL)
    {
        if (src->val < x)
        {
            Smalltail->next = src;
            Smalltail = src;
        }
        else {
            Bigtail->next = src;
            Bigtail = src;
        }
        src = src->next;
    }
    Smalltail->next = Bighead->next;
    Bigtail->next = NULL;
    return Smallhead->next;
}
